package com.atguigu.structures.tree;

import com.atguigu.structures.tree.node.TreeNode;

/**
 * 线索化二叉树-中序，遍历
 *
 * @author xr-8
 * @date 2022-10-22
 * @time 23:09
 */
public class ThreadedBinaryTree {

    private TreeNode root;

    // 为了实现线索化，需要创建要给指向当前节点的前驱节点的指针
    // 在递归进行线索化时，pre总是保留前一个节点
    private TreeNode pre;

    /**
     * 对二叉树进行中序线索化
     */
    public void threadedNodes() {
        this.threadedNodes(root);
    }

    /**
     * 对二叉树进行中序线索化
     * @param node
     */
    private void threadedNodes(TreeNode node) {
        if (node == null) {
            return;
        }

        // 1、先线索化左子树
        threadedNodes(node.getLeft());

        // 2、线索化当前节点
        // 处理前驱节点
        if (/*pre != null && */node.getLeft() == null) { // 这里不判断pre!=null，当线索化8（中序遍历时的第一个结点）时，尽管她没有前驱节点，也要把leftType置为1，方便后面的遍历。
            node.setLeft(pre);
            node.setLeftType(1);
        }
        // 处理后继节点
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        // 移动pre指针
        pre = node;

        // 3、再线索化右子树
        threadedNodes(node.getRight());
    }

    /**
     * 遍历中序线索化后的二叉树
     */
    public void threadList() {
        TreeNode node = root;
        while(node != null) {
            // 找到node的左子树的起始节点，并输出
            while(node.getLeftType() == 0) {
                node = node.getLeft();
            }
            System.out.println(node);

            // 如果当前节点的右指针指向的是后继节点，则一直输出
            while (node.getRightType() == 1) {
                // 获取当前节点的后继节点并输出
                node = node.getRight();
                System.out.println(node);
            }

            // 如果当前节点的右指针指向的不是后继节点，则移动node指针
            // 即按照中序遍历的规则，当前节点的左子树已经遍历完成，该遍历当前节点的右子树。所以移动指针到当前节点的右节点，重复以上动作
            node = node.getRight();
        }

    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public TreeNode getPre() {
        return pre;
    }

    public void setPre(TreeNode pre) {
        this.pre = pre;
    }

}
